package com.gxc.array;

import com.gxc.print.ArrayPrint;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 57. 插入区间
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，
 * 其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，
 * 并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end]
 * 表示另一个区间的开始和结束。
 *
 * 在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，
 * 且区间之间不重叠（如果有必要的话，可以合并区间）。
 *
 * 返回插入之后的 intervals。
 *
 * 注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它
 */
public class Insert {

    public static void main(String[] args) {
        ArrayPrint.print(handle(new int[][]{
                {1,3},{6,9}
        }, new int[]{2,5}));

        ArrayPrint.print(handle(new int[][]{
                {1,2},{3,5},{6,7},{8,10},{12,16}
        }, new int[]{4,8}));
    }

    public static int[][] handle(int[][] intervals, int[] newInterval) {
        List<List<Integer>> list = new ArrayList<>();

        int min = newInterval[0];
        int max = newInterval[1];
        for (int i = 0; i < intervals.length; i++) {
            int[] interval = intervals[i];
            if (interval[1] < min || interval[0]>max) {
                List<Integer> arr = new ArrayList<>();
                arr.add(interval[0]);
                arr.add(interval[1]);
                list.add(arr);
            } else {
                min = Math.min(interval[0], min);
                max = Math.max(interval[1], max);
            }
        }

        List<Integer> arr = new ArrayList<>();
        arr.add(min);
        arr.add(max);
        list.add(arr);

        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i][0] = list.get(i).get(0);
            res[i][1] = list.get(i).get(1);
        }
        Arrays.sort(res, (o1, o2) -> o1[0] - o2[0]);
        return res;
    }

    class Solution {
        public int[][] insert(int[][] intervals, int[] newInterval) {
            int left = newInterval[0];
            int right = newInterval[1];
            boolean placed = false;
            List<int[]> ansList = new ArrayList<int[]>();
            for (int[] interval : intervals) {
                if (interval[0] > right) {
                    // 在插入区间的右侧且无交集
                    if (!placed) {
                        ansList.add(new int[]{left, right});
                        placed = true;
                    }
                    ansList.add(interval);
                } else if (interval[1] < left) {
                    // 在插入区间的左侧且无交集
                    ansList.add(interval);
                } else {
                    // 与插入区间有交集，计算它们的并集
                    left = Math.min(left, interval[0]);
                    right = Math.max(right, interval[1]);
                }
            }
            if (!placed) {
                ansList.add(new int[]{left, right});
            }
            int[][] ans = new int[ansList.size()][2];
            for (int i = 0; i < ansList.size(); ++i) {
                ans[i] = ansList.get(i);
            }
            return ans;
        }
    }


}
